package Array;

import java.util.Arrays;

public class Fibonacci {
    public static void main(String[] args) {
        int[] arr={1,2,3,45,67,77,87};
        System.out.println(f(arr,77 ));
    }
    public static int[] fib(){
        int[] arr=new int[20];
        arr[0]=1;
        arr[1]=1;
        for (int i = 2; i < arr.length; i++) {
            arr[i]=arr[i-1]+arr[i-2];
        }
        return arr;
    }
    public static int f(int[] arr,int values){
        int low=0;//左索引
        int hight=arr.length-1;//右索引
        int mid=0;//中间值下表
        int k=0;//斐波那契数下表，low+F(k-1)
        int F[]=fib();//获取斐波那契数列
        while (hight>F[k]-1){
            k++;
        }
        //copyOf()的第二个自变量指定要建立的新数组长度，如果新数组的长度超过原数组的长度，则保留数组默认值
        //因为f[k]值可能大于数组a的长度，因此我们需要使用Arrays类，构造新的数组，并指向a
        //不足的部分会使用0填充
        int[] temp= Arrays.copyOf(arr,F[k]);
        for (int i = hight+1; i < k; i++) {
            temp[i]=arr[hight];//将后面的值变成数组arr最后一个值
        }
        while (low<=hight){
            mid=low+F[k-1]-1;
            if (temp[mid]<values){
                low=mid+1;
                //说明：
                //1、全部的元素=前面的元素+后面的元素
                //2、f[k] = f[k-1]+f[k-2]
                //3、因为后面有f[k-2]，所以可以继续拆分 f[k-1] = f[k-3] +f[k-4]
                //4、即在f[k-2]的前面进行查找 k-=2
                //即下次循环的时候 mid = f[k-1-2]-1
                k-=2;
            } else if (temp[mid]>values){
                hight=mid-1;
                //说明
                //1、全部的元素=前面的元素+后面的元素
                //2、f[k] = f[k-1]+f[k-2]
                //因为前面有f[k-1]个元素，所以可以继续拆分  f[k-1] = f[k-2]+f[k-3]
                //即在f[k-1]的前面继续查找，k--
                //即下次循环的时候 mid = f[k-1-1]-1
                k-=1;
            }else {//找到了
                if (mid<=hight){
                    return mid;
                }else {
                    return hight;
                }
            }
        }
        return -1;
    }
}
